<!DOCTYPE HTML>
<html lang="zh-CN">
<head>
    <meta charset="UTF-8" />
    <meta http-equiv="X-UA-Compatible" content="IE=edge,chrome=1" />
    <meta name="viewport" content="width=device-width, initial-scale=1, maximum-scale=1" /> 
    <title> - 天地维杰网</title>
    <meta name="keywords" content="系统架构,shutdown,不与天斗,Domino,博客,程序员,架构师,笔记,技术,分享,java,Redis">
    
    <meta property="og:title" content="">
    <meta property="og:site_name" content="天地维杰网">
    <meta property="og:image" content="/img/author.jpg"> 
    <meta name="title" content=" - 天地维杰网" />
    <meta name="description" content="天地维杰网 | 博客 | 软件 | 架构 | Java "> 
    <link rel="shortcut icon" href="http://www.shutdown.cn/img/favicon.ico" />
    <link rel="apple-touch-icon" href="http://www.shutdown.cn/img/apple-touch-icon.png" />
    <link rel="apple-touch-icon-precomposed" href="http://www.shutdown.cn/img/apple-touch-icon.png" />
    <link href="http://www.shutdown.cn/js/vendor/font-awesome/css/font-awesome.min.css?v=4.6.2" rel="stylesheet" type="text/css" />
    <link href="http://www.shutdown.cn/js/vendor/fancybox/jquery.fancybox.css?v=2.1.5" rel="stylesheet" type="text/css" />
    <link href="http://www.shutdown.cn/css/main.css" rel="stylesheet" type="text/css" />
    <link href="http://www.shutdown.cn/css/syntax.css" rel="stylesheet" type="text/css" />
    <script type="text/javascript" id="hexo.configuration">
  var NexT = window.NexT || {};
  var CONFIG = {
    scheme: 'Pisces',
    sidebar: {"position":"left","display":"post"},
     fancybox: true, 
    motion: true
  };
</script>
<script async src="https://pagead2.googlesyndication.com/pagead/js/adsbygoogle.js?client=ca-pub-7826003325059020" crossorigin="anonymous"></script>
</head>
<body itemscope itemtype="http://schema.org/WebPage" lang="zh-Hans">
<div class="container one-collumn sidebar-position-left page-home  ">
    <div class="headband"></div>

    <header id="header" class="header" itemscope itemtype="http://schema.org/WPHeader">
      <div class="header-inner"> <div class="site-meta  custom-logo ">

  <div class="custom-logo-site-title">
    <a href="http://www.shutdown.cn"  class="brand" rel="start">
      <span class="logo-line-before"><i></i></span>
      <span class="site-title">天地维杰网</span>
      <span class="logo-line-after"><i></i></span>
    </a>
  </div>
  <p class="site-subtitle">人如秋鸿来有信，事若春梦了无痕</p>
</div>

<div class="site-nav-toggle">
  <button>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
    <span class="btn-bar"></span>
  </button>
</div>

<nav class="site-nav">
    <ul id="menu" class="menu">
      
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-home"></i> <br />首页
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/redis/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-battery-full"></i> <br />Redis
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/java/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-coffee"></i> <br />java
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/linux/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-linux"></i> <br />linux
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/daily/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-bug"></i> <br />日常问题
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/spring/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-child"></i> <br />Spring和Springboot
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/mac/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-fire"></i> <br />Mac相关
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/middleware/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-gavel"></i> <br />中间件
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/jiagou/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-rocket"></i> <br />架构
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/python/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-ship"></i> <br />python
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/front/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-bolt"></i> <br />前端
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/jvm/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-balance-scale"></i> <br />jvm
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/c/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-battery-empty"></i> <br />c语言
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/categories/web3/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-web3"></i> <br />web3
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/post/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-archive"></i> <br />归档
          </a>
        </li>
      
        <li class="menu-item ">
          <a href="http://www.shutdown.cn/about/" rel="section">
              <i class="menu-item-icon fa fa-fw fa-user"></i> <br />关于
          </a>
        </li>
      
      <li class="menu-item menu-item-search">
        <a href="javascript:;" class="popup-trigger"> <i class="menu-item-icon fa fa-search fa-fw"></i> <br /> 搜索</a>
      </li>
    </ul>
    <div class="site-search">
      <div class="popup">
 <span class="search-icon fa fa-search"></span>
 <input type="text" id="local-search-input">
 <div id="local-search-result"></div>
 <span class="popup-btn-close">close</span>
</div>

    </div>
</nav>

 </div>
    </header>

    <main id="main" class="main">
      <div class="main-inner">
        <div class="content-wrap">
          <div id="content" class="content">
            
<section id="posts" class="posts-expand">
  <article class="post post-type-normal " itemscope itemtype="http://schema.org/Article">
    <header class="post-header">
      <h1 class="post-title" itemprop="name headline">
        <a class="post-title-link" href="http://www.shutdown.cn/post/redis5.0%E4%BC%98%E5%8C%96-jemalloc5.1%E4%B8%80%E5%AE%9E%E7%8E%B0%E5%8E%9F%E7%90%86%E5%88%86%E6%9E%90/" itemprop="url">
        
        </a>
      </h1>
      <div class="post-meta">
      <span class="post-time">
<span class="post-meta-item-icon">
    <i class="fa fa-calendar-o"></i>
</span>
<span class="post-meta-item-text">时间：</span>
<time itemprop="dateCreated" datetime="2016-03-22T13:04:35+08:00" content="0001-01-01">
    0001-01-01
</time>
</span> 
      
      
       <span>
&nbsp; | &nbsp;
<span class="post-meta-item-icon">
    <i class="fa fa-eye"></i>
</span>
<span class="post-meta-item-text">阅读：</span>
<span class="leancloud-visitors-count">996 字 ~5分钟</span>
</span>
      </div>
    </header>
    <div class="post-body" itemprop="articleBody">
    

    

<h1 id="database-内存管理-jemalloc-5-1-0-实现分析">Database · 内存管理 · JeMalloc-5.1.0 实现分析</h1>

<blockquote>
<p>源文地址：<a href="https://www.bookstack.cn/read/aliyun-rds-core/4a0cdf677f62feb3.md">https://www.bookstack.cn/read/aliyun-rds-core/4a0cdf677f62feb3.md</a></p>
</blockquote>

<p>JeMalloc 是一款内存分配器，与其它内存分配器相比，它最大的优势在于多线程情况下的高性能以及内存碎片的减少。</p>

<p>这篇文章介绍 <strong>JeMalloc-5.1.0</strong> 版本（release 日期：2018年5月9日）的实现细节。</p>

<p>对于对老版本比较熟悉的人来说，有几点需要说明：</p>

<ol>
<li>chunk 这一概念被替换成了 extent</li>
<li>dirty page 的 decay（或者说 gc） 变成了两阶段，dirty -&gt; muzzy -&gt; retained</li>
<li>huge class 这一概念不再存在</li>
<li>红黑树不再使用，取而代之的是 pairing heap</li>
</ol>

<h2 id="基础知识">基础知识</h2>

<p>以下内容介绍 JeMalloc 中比较重要的概念以及数据结构。</p>

<h4 id="size-class">size_class</h4>

<p>每个 <code>size_class</code> 代表 jemalloc 分配的内存大小，共有 NSIZES（232）个小类（如果用户申请的大小位于两个小类之间，会取较大的，比如申请14字节，位于8和16字节之间，按16字节分配），分为2大类：</p>

<ul>
<li><code>small_class</code>（*小内存*） : 对于64位机器来说，通常区间是 [8, 14kb]，常见的有 8, 16, 32, 48, 64, …, 2kb, 4kb, 8kb，注意为了减少内存碎片并不都是2的次幂，比如如果没有48字节，那当申请33字节时，分配64字节显然会造成约50%的内存碎片</li>
<li><code>large_class</code>（*大内存*）: 对于64位机器来说，通常区间是 [16kb, 7EiB]，从 4 * page_size 开始，常见的比如 16kb, 32kb, …, 1mb, 2mb, 4mb，最大是 $2^{62}+3^{60}$</li>
<li><code>size_index</code> : size 位于 <code>size_class</code> 中的索引号，区间为 [0，231]，比如8字节则为0，14字节（按16计算）为1，4kb字节为28，当 size 是 <code>small_class</code> 时，<code>size_index</code> 也称作 <code>binind</code></li>
</ul>

<h4 id="base">base</h4>

<p>用于分配 jemalloc 元数据内存的结构，通常一个 <code>base</code> 大小为 2mb， 所有 <code>base</code> 组成一个链表。</p>

<ul>
<li><code>base.extents[NSIZES]</code> : 存放每个 <code>size_class</code> 的 <code>extent</code> 元数据</li>
</ul>

<h4 id="bin">bin</h4>

<p>管理正在使用中的 <code>slab</code>（即用于小内存分配的 <code>extent</code>） 的集合，每个 <code>bin</code> 对应一个 <code>size_class</code></p>

<ul>
<li><code>bin.slabcur</code> : 当前使用中的 <code>slab</code></li>
<li><code>bin.slabs_nonfull</code> : 有空闲内存块的 <code>slab</code></li>
</ul>

<h4 id="extent">extent</h4>

<p>管理 jemalloc 内存块（即用于用户分配的内存）的结构，每一个内存块大小可以是 <code>N * page_size(4kb)</code>（N &gt;= 1）。每个 extent 有一个序列号（serial number）。</p>

<p>一个 <code>extent</code> 可以用来分配一次 <code>large_class</code> 的内存申请，但可以用来分配多次 <code>small_class</code> 的内存申请。</p>

<ul>
<li><code>extent.e_bits</code> : 8字节长，记录多种信息</li>
<li><code>extent.e_addr</code> : 管理的内存块的起始地址</li>
<li><code>extent.e_slab_data</code> : 位图，当此 <code>extent</code> 用于分配 <code>small_class</code> 内存时，用来记录这个 <code>extent</code> 的分配情况，此时每个 <code>extent</code> 的内的小内存称为 <code>region</code></li>
</ul>

<h4 id="slab">slab</h4>

<p>当 extent 用于分配 <code>small_class</code> 内存时，称其为 <code>slab</code>。一个 <code>extent</code> 可以被用来处理多个同一 <code>size_class</code> 的内存申请。</p>

<h4 id="extents">extents</h4>

<p>管理 <code>extent</code> 的集合。</p>

<ul>
<li><code>extents.heaps[NPSIZES+1]</code> : 各种 <code>page(4kb)</code> 倍数大小的 <code>extent</code></li>
<li><code>extents.lru</code> : 存放所有 <code>extent</code> 的双向链表</li>
<li><code>extents.delay_coalesce</code> : 是否延迟 <code>extent</code> 的合并</li>
</ul>

<h4 id="arena">arena</h4>

<p>用于分配&amp;回收 <code>extent</code> 的结构，每个用户线程会被绑定到一个 <code>arena</code> 上，默认每个逻辑 CPU 会有 4 个 <code>arena</code> 来减少锁的竞争，各个 arena 所管理的内存相互独立。</p>

<ul>
<li><code>arena.extents_dirty</code> : 刚被释放后空闲 <code>extent</code> 位于的地方</li>
<li><code>arena.extents_muzzy</code> : <code>extents_dirty</code> 进行 lazy purge 后位于的地方，<code>dirty -&gt; muzzy</code></li>
<li><code>arena.extents_retained</code> : <code>extents_muzzy</code> 进行 decommit 或 force purge 后 <code>extent</code> 位于的地方，<code>muzzy -&gt; retained</code></li>
<li><code>arena.large</code> : 存放 <code>large extent</code> 的 <code>extents</code></li>
<li><code>arena.extent_avail</code> : heap，存放可用的 <code>extent</code> 元数据</li>
<li><code>arena.bins[NBINS]</code> : 所以用于分配小内存的 <code>bin</code></li>
<li><code>arena.base</code> : 用于分配元数据的 <code>base</code></li>
</ul>

<table>
<thead>
<tr>
<th align="left">内存状态</th>
<th align="left">备注</th>
</tr>
</thead>

<tbody>
<tr>
<td align="left">clean</td>
<td align="left">分配给用户或 <code>tcache</code></td>
</tr>

<tr>
<td align="left">dirty</td>
<td align="left">用户调用 free 或 <code>tcache</code> 进行了 gc</td>
</tr>

<tr>
<td align="left">muzzy</td>
<td align="left"><code>extents_dirty</code> 对 <code>extent</code> 进行 lazy purge</td>
</tr>

<tr>
<td align="left">retained</td>
<td align="left"><code>extents_muzzy</code> 对 <code>extent</code> 进行了 decommit 或 force purge</td>
</tr>
</tbody>
</table>

<blockquote>
<p>purge 及 decommit 在内存 gc 模块介绍</p>
</blockquote>

<h4 id="rtree">rtree</h4>

<p>全局唯一的存放每个 <code>extent</code> 信息的 Radix Tree，以 <code>extent-&gt;e_addr</code> 即 <code>uintptr_t</code> 为 key，以我的机器为例，<code>uintptr_t</code> 为64位（8字节）， <code>rtree</code> 的高度为3，由于 <code>extent-&gt;e_addr</code> 是 <code>page(1 &lt;&lt; 12)</code> 对齐的，也就是说需要 64 - 12 = 52 位即可确定在树中的位置，每一层分别通过第0-16位，17-33位，34-51位来进行访问。</p>

<div  align="center"><img src="https://wejack639.oss-cn-beijing.aliyuncs.com/blogimages/img/20220620155508.png" width = 900 /> </div>

<h4 id="cache-bin">cache_bin</h4>

<p>每个线程独有的用于分配小内存的缓存</p>

<ul>
<li><code>low_water</code> : 上一次 gc 后剩余的缓存数量</li>
<li><code>cache_bin.ncached</code> : 当前 <code>cache_bin</code> 存放的缓存数量</li>
<li><code>cache_bin.avail</code> : 可直接用于分配的内存，从左往右依次分配（注意这里的寻址方式）</li>
</ul>

<div  align="center"><img src="https://wejack639.oss-cn-beijing.aliyuncs.com/blogimages/img/20220620155524.png" width = 900 /> </div>

<h4 id="tcache">tcache</h4>

<p>每个线程独有的缓存（Thread Cache），大多数内存申请都可以在 <code>tcache</code> 中直接得到，从而避免加锁</p>

<ul>
<li><code>tcache.bins_small[NBINS]</code> : 小内存的 <code>cache_bin</code></li>
</ul>

<h4 id="tsd">tsd</h4>

<p>Thread Specific Data，每个线程独有，用于存放与这个线程相关的结构</p>

<ul>
<li><code>tsd.rtree_ctx</code> : 当前线程的 rtree context，用于快速访问 <code>extent</code> 信息</li>
<li><code>tsd.arena</code> : 当前线程绑定的 <code>arena</code></li>
<li><code>tsd.tcache</code> : 当前线程的 <code>tcache</code></li>
</ul>

<h2 id="内存分配-malloc">内存分配（malloc）</h2>

<h4 id="小内存-small-class-分配">小内存(small_class)分配</h4>

<p>首先从 <code>tsd-&gt;tcache-&gt;bins_small[binind]</code> 中获取对应 <code>size_class</code> 的内存，有的话将内存直接返回给用户，如果 <code>bins_small[binind]</code> 中没有的话，需要通过 <code>slab(extent)</code> 对 <code>tsd-&gt;tcache-&gt;bins_small[binind]</code> 进行填充，一次填充多个以备后续分配，填充方式如下（当前步骤无法成功则进行下一步）：</p>

<ol>
<li>通过 <code>bin-&gt;slabcur</code> 分配</li>
<li>从 <code>bin-&gt;slabs_nonfull</code> 中获取可使用的 <code>extent</code></li>
<li>从 <code>arena-&gt;extents_dirty</code> 中回收 <code>extent</code>，回收方式为 *<strong>best-fit*</strong>，即满足大小要求的<strong>最小</strong> <code>extent</code>，在 <code>arena-&gt;extents_dirty-&gt;bitmap</code> 中找到满足大小要求并且第一个非空 heap 的索引 <code>i</code>，然后从 <code>extents-&gt;heaps[i]</code> 中获取第一个 <code>extent</code>。由于 <code>extent</code> 可能较大，为了防止产生内存碎片，需要对 <code>extent</code> 进行分裂（伙伴算法），然后将分裂后不使用的 <code>extent</code> 放回 <code>extents_dirty</code> 中</li>
<li>从 <code>arena-&gt;extents_muzzy</code> 中回收 <code>extent</code>，回收方式为 *<strong>first-fit*</strong>，即满足大小要求且<strong>序列号最小地址最低（最旧）</strong>的 <code>extent</code>，遍历每个满足大小要求并且非空的 <code>arena-&gt;extents_dirty-&gt;bitmap</code>，获取其对应 <code>extents-&gt;heaps</code> 中第一个 <code>extent</code>，然后进行比较，找到最旧的 <code>extent</code>，之后仍然需要分裂</li>
<li>从 <code>arena-&gt;extents_retained</code> 中回收 <code>extent</code>，回收方式与 <code>extents_muzzy</code> 相同</li>
<li>尝试通过 <code>mmap</code> 向内核获取所需的 <code>extent</code> 内存，并且在 <code>rtree</code> 中注册新 <code>extent</code> 的信息</li>
<li>再次尝试从 <code>bin-&gt;slabs_nonfull</code> 中获取可使用的 <code>extent</code></li>
</ol>

<p>简单来说，这个流程是这样的，<code>cache_bin -&gt; slab -&gt; slabs_nonfull -&gt; extents_dirty -&gt; extents_muzzy -&gt; extents_retained -&gt; kernal</code>。</p>

<div  align="center"><img src="https://wejack639.oss-cn-beijing.aliyuncs.com/blogimages/img/20220620155537.png" width = 900 /> </div>

<h4 id="大内存-large-class-分配">大内存(large_class)分配</h4>

<p>大内存不存放在 <code>tsd-&gt;tcache</code> 中，因为这样可能会浪费内存，所以每次申请都需要重新分配一个 <code>extent</code>，申请的流程和小内存申请 <code>extent</code> 流程中的3, 4, 5, 6是一样的。</p>

<h2 id="内存释放-free">内存释放（free）</h2>

<h4 id="小内存释放">小内存释放</h4>

<p>在 <code>rtree</code> 中找到需要被释放内存所属的 <code>extent</code> 信息，将要被释放的内存还给 <code>tsd-&gt;tcache-&gt;bins_small[binind]</code>，如果 <code>tsd-&gt;tcache-&gt;bins_small[binind]</code> 已满，需要对其进行 flush，流程如下：</p>

<ol>
<li>将这块内存返还给所属 <code>extent</code>，如果这个 <code>extent</code> 中空闲的内存块变成了最大（即没有一份内存被分配），跳到2；如果这个 <code>extent</code> 中的空闲块变成了1并且这个 <code>extent</code> 不是 <code>arena-&gt;bins[binind]-&gt;slabcur</code>，跳到3</li>
<li>将这个 <code>extent</code> 释放，即插入 <code>arena-&gt;extents_dirty</code> 中</li>
<li>将 <code>arena-&gt;bins[binind]-&gt;slabcur</code> 切换为这个 <code>extent</code>，前提是这个 <code>extent</code> “更旧”（序列号更小地址更低），并且将替换后的 <code>extent</code> 移入 <code>arena-&gt;bins[binind]-&gt;slabs_nonfull</code></li>
</ol>

<h4 id="大内存释放">大内存释放</h4>

<p>因为大内存不存放在 <code>tsd-&gt;tcache</code> 中，所以大内存释放只进行小内存释放的步骤2，即将 <code>extent</code> 插入 <code>arena-&gt;extents_dirty</code> 中。</p>

<h2 id="内存再分配-realloc">内存再分配（realloc）</h2>

<h4 id="小内存再分配">小内存再分配</h4>

<ol>
<li>尝试进行 <code>no move</code> 分配，如果两次申请位于同一 <code>size class</code> 的话就可以不做任何事情，直接返回。比如第一次申请了12字节，但实际上 jemalloc 会实际分配16字节，然后第二次申请将12扩大到15字节或者缩小到9字节，那这时候16字节就已经满足需求了，所以不做任何事情，如果无法满足，跳到2</li>
<li>重新分配，申请新内存大小（参考<strong>内存分配</strong>），然后将旧内存内容拷贝到新地址，之后释放旧内存（参考<strong>内存释放</strong>），最后返回新内存</li>
</ol>

<h4 id="大内存再分配">大内存再分配</h4>

<ol>
<li>尝试进行 <code>no move</code> 分配，如果两次申请位于同一 <code>size class</code> 的话就可以不做任何事情，直接返回。</li>
<li>尝试进行 <code>no move resize</code> 分配，如果第二次申请的大小大于第一次，则尝试对当前地址所属 <code>extent</code> 的下一地址查看是否可以分配，比如当前 <code>extent</code> 地址是 0x1000，大小是 0x1000，那么我们查看地址 0x2000 开始的 <code>extent</code> 是否存在（通过 <code>rtree</code>）并且是否满足要求，如果满足要求那两个 <code>extent</code> 可以进行合并，成为一个新的 <code>extent</code> 而不需要重新分配；如果第二次申请的大小小于第一次，那么尝试对当前 <code>extent</code> 进行 split，移除不需要的后半部分，以减少内存碎片；如果无法进行 <code>no move resize</code> 分配，跳到3</li>
<li>重新分配，申请新内存大小（参考<strong>内存分配</strong>），然后将旧内存内容拷贝到新地址，之后释放旧内存（参考<strong>内存释放</strong>），最后返回新内存</li>
</ol>

<h2 id="内存-gc">内存 GC</h2>

<p>分为2种， <code>tcache</code> 和 <code>extent</code> GC。其实更准确来说是 decay，为了方便还是用 gc 吧。</p>

<h3 id="tcache-gc">tcache GC</h3>

<p>针对 <code>small_class</code>，防止某个线程预先分配了内存但是却没有实际分配给用户，会定期将缓存 flush 到 <code>extent</code>。</p>

<p><strong>GC 策略</strong></p>

<p>每次对于 <code>tcache</code> 进行 malloc 或者 free 操作都会执行一次计数，默认情况下达到228次就会触发 gc，每次 gc 一个 <code>cache_bin</code>。</p>

<p><strong>如何 GC</strong></p>

<ol>
<li><code>cache_bin.low_water &gt; 0</code> : gc 掉 <code>low_water</code> 的 3/4，同时，将 <code>cache_bin</code> 能缓存的最大数量缩小一倍</li>
<li><code>cache_bin.low_water &lt; 0</code> : 将 <code>cache_bin</code> 能缓存的最大数量增大一倍</li>
</ol>

<p>总的来说保证当前 <code>cache_bin</code> 分配越频繁，则会缓存更多的内存，否则则会减少。</p>

<h3 id="extent-gc">extent GC</h3>

<p><strong>调用 free 时，内存并没有归还给内核</strong>。 jemalloc 内部会不定期地将没有用于分配的 <code>extent</code> 逐步 GC，流程和内存申请是反向的， <code>free -&gt; extents_dirty -&gt; extents_muzzy -&gt; extents_retained -&gt; kernal</code>。</p>

<p><strong>GC 策略</strong></p>

<p>默认10s为 <code>extents_dirty</code> 和 <code>extents_muzzy</code> 的一个 gc 周期，每次对于 <code>arena</code> 进行 malloc 或者 free 操作都会执行一次计数，达到1000次会检测有没有达到 gc 的 deadline，如果是的话进行 gc。</p>

<p>注意并不是每隔10s一次性 gc，实际上 jemalloc 会将10s划分成200份，即每隔0.05s进行一次 gc，这样一来如果 t 时刻有 N 个 <code>page</code> 需要 gc，那么 jemalloc 尽力保证在 t+10 时刻这 N 个 <code>page</code> 会被 gc 完成。</p>

<p>严格来说，对于两次 gc 时刻 $t<em>{1}$ 和 $t</em>{2}$，在 $t<em>{2}-t</em>{1}$ 时间段内产生的所有 <code>page</code>（dirty page 或 muzzy page） 会在 ($t<em>{2}$, $ t</em>{2}+10$] 被 gc 完成。</p>

<p>对于 N 个需要 gc 的 <code>page</code> 来说，并不是简单地每0.05s处理 N/200 个 <code>page</code>，jemalloc 引入了 <strong><code>Smoothstep</code></strong>（主要用于计算机图形学）来获得更加平滑的 gc 机制，这是 jemalloc 非常有意思的一个点。</p>

<div  align="center"><img src="https://wejack639.oss-cn-beijing.aliyuncs.com/blogimages/img/20220620155550.png" width = 600 /> </div>

<p>jemalloc 内部维护了一个长度为200的数组，用来计算在10s的 gc 周期内每个时间点应该对多少 <code>page</code> 进行 gc。这样保证两次 gc 的时间段内产生的需要 gc 的 <code>page</code> 都会以图中绿色线条（默认使用 smootherstep）的变化曲线在10s的周期内从 N 减为 0（从右往左）。</p>

<p><strong>如何 GC</strong></p>

<p>先进行 <code>extents_dirty</code> 的 gc，后进行 <code>extents_muzzy</code> 。</p>

<ul>
<li>将 <code>extents_dirty</code> 中的 <code>extent</code> 移入 <code>extents_muzzy</code>：

<ol>
<li>在 <code>extents_dirty</code> 中的 LRU 链表中，获得要进行 gc 的 <code>extent</code>，尝试对 <code>extent</code> 进行前后合并（前提是两个 <code>extent</code> 位于同一 <code>arena</code> 并且位于同一 <code>extents</code> 中），获得新的 <code>extent</code>，然后将其移除</li>
<li>对当前 <code>extent</code> 管理的地址进行 lazy purge，即通过 <code>madvise</code> 使用 <code>MADV_FREE</code> 参数告诉内核当前 <code>extent</code> 管理的内存可能不会再被访问</li>
<li>在 <code>extents_muzzy</code> 中尝试对当前 <code>extent</code> 进行前后合并，获得新的 <code>extent</code>，最后将其插入 <code>extents_muzzy</code></li>
</ol></li>
<li>将 <code>extents_muzzy</code> 中的 <code>extent</code> 移入 <code>extents_retained</code> :

<ol>
<li>在 <code>extents_muzzy</code> 中的 LRU 链表中，获得要进行 gc 的 <code>extent</code>，尝试对 <code>extent</code> 进行前后合并，获得新的 <code>extent</code>，然后将其移除</li>
<li>对当前 <code>extent</code> 管理的地址进行 decommit，即调用 <code>mmap</code> 带上 <code>PROT_NONE</code> 告诉内核当前 <code>extent</code> 管理的地址可能不会再被访问，如果 decommit 失败，会进行 force purge，即通过 <code>madvise</code> 使用 <code>MADV_DONTNEED</code> 参数告诉内核当前 <code>extent</code> 管理的内存可能不会再被访问</li>
<li>在 <code>extents_retained</code> 中尝试对当前 <code>extent</code> 进行前后合并，获得新的 <code>extent</code>，最后将其插入 <code>extents_retained</code></li>
</ol></li>
<li>jemalloc 默认不会将内存归还给内核，只有进程结束时，所有内存才会 <code>munmap</code>，从而归还给内核。不过可以手动进行 <code>arena</code> 的销毁，从而将 <code>extents_retained</code> 中的内存进行 <code>munmap</code></li>
</ul>

<h2 id="内存碎片">内存碎片</h2>

<p>JeMalloc 保证内部碎片在20%左右。对于绝大多数 <code>size_class</code> 来说，都属于 $2^{x}$ 的 group $y$，比如 160，192，224，256都属于 $2^{8-1}$ 的 group 7。对于一个 group 来说，会有4个 <code>size_class</code>，每个 size 的大小计算是这样的，$(1 « y) + (i « (y-2))$，其中 i 为在这个 group 中的索引（1，2，3，4），比如 160 为 $(1 « 7) + (1 « 5)$，即 $5 * 2^{7-2}$。</p>

<p>对于两组 group 来说：</p>

<table>
<thead>
<tr>
<th align="left">Group</th>
<th align="left">Size</th>
</tr>
</thead>

<tbody>
<tr>
<td align="left">y</td>
<td align="left">$5 <em>2^{y-2}$, $6</em> 2^{y-2}$, $7 <em>2^{y-2}$, $8</em> 2^{y-2}$</td>
</tr>

<tr>
<td align="left">y+1</td>
<td align="left">$5 <em>2^{y-1}$, $6</em> 2^{y-1}$, $7 <em>2^{y-1}$, $8</em> 2^{y-1}$</td>
</tr>
</tbody>
</table>

<p>取相差最大的第一组的最后一个和第二组的第一个，内存碎片约为 $\frac{5 * 2^{y-1} - 8 * 2^{y-2} + 1}{5 * 2^{y-1}}$ 约等于 20%。</p>

<h2 id="jemalloc-实现上的优缺点">JeMalloc 实现上的优缺点</h2>

<h4 id="优点">优点</h4>

<ol>
<li>采用多个 <code>arena</code> 来避免线程同步</li>
<li>细粒度的锁，比如每一个 <code>bin</code> 以及每一个 <code>extents</code> 都有自己的锁</li>
<li>Memory Order 的使用，比如 <code>rtree</code> 的读写访问有不同的原子语义（relaxed, acquire, release）</li>
<li>结构体以及内存分配时保证对齐，以获得更好的 cache locality</li>
<li><code>cache_bin</code> 分配内存时会通过栈变量来判断是否成功以避免 cache miss</li>
<li>dirty <code>extent</code> 的 delay coalesce 来获得更好的 cache locality；<code>extent</code> 的 lazy purge 来保证更平滑的 gc 机制</li>
<li>紧凑的结构体内存布局来减少占用空间，比如 <code>extent.e_bits</code></li>
<li><code>rtree</code> 引入 <code>rtree_ctx</code> 的两级 <code>cache</code> 机制，提升 <code>extent</code> 信息获取速度的同时减少 cache miss</li>
<li><code>tcache</code> gc 时对缓存容量的动态调整</li>
</ol>

<h4 id="缺点">缺点</h4>

<ol>
<li><div class="highlight"><pre style="background-color:#f8f8f8;-moz-tab-size:4;-o-tab-size:4;tab-size:4"><code class="language-fallback" data-lang="fallback">arena</code></pre></div></li>
</ol>

<p>之间的内存不可见</p>

<ul>
<li>某个线程在这个 <code>arena</code> 使用了很多内存，之后这个 <code>arena</code> 并没有其他线程使用，导致这个 <code>arena</code> 的内存无法被 gc，占用过多</li>
<li>两个位于不同 <code>arena</code> 的线程频繁进行内存申请，导致两个 <code>arena</code> 的内存出现大量交叉，但是连续的内存由于在不同 <code>arena</code> 而无法进行合并</li>
</ul>

<ol>
<li>目前只想到了一个</li>
</ol>

<h2 id="总结">总结</h2>

<p>文章开头说 JeMalloc 的优点在于多线程下的性能以及内存碎片的减少，对于保证多线程性能，有不同 <code>arena</code>、降低锁的粒度、使用原子语义等等；对于内存碎片的减少，有经过设计的多种 <code>size_class</code>、伙伴算法、gc 等等。</p>

<p>阅读 JeMalloc 源码的意义不光在于能够精确描述每次 malloc 和 free 会发生什么，还在于学习内存分配器如何管理内存。malloc 和 free 是静态的释放和分配，而 <code>tcache</code> 和 <code>extent</code> 的 gc 则是动态的管理，熟悉后者同样非常重要。</p>

<p>除此以外还能够帮助自己在编程时根据相应的内存使用特征去选择合适的内存分配方法，甚至使用自己实现的特定内存分配器。</p>

<p>最后个人觉得 jemalloc 最有意思的地方就在于 <code>extent</code> 的曲线 gc 了。</p>

<h2 id="参考">参考</h2>

<p><a href="http://jemalloc.net/jemalloc.3.html">JeMalloc</a></p>

<p><a href="https://youjiali1995.github.io/allocator/jemalloc/">JeMalloc-4.0.3</a></p>

<p><a href="https://youjiali1995.github.io/allocator/jemalloc-purge/">JeMalloc-Purge</a></p>

<p><a href="https://zhuanlan.zhihu.com/p/29216091">图解 TCMalloc</a></p>

<p><a href="https://zhuanlan.zhihu.com/p/29415507">TCMalloc分析 - 如何减少内存碎片</a></p>

<p><a href="http://goog-perftools.sourceforge.net/doc/tcmalloc.html">TCMalloc</a></p>

    </div>
    <footer class="post-footer">
     

     <div class="post-nav">
    <div class="post-nav-next post-nav-item">
    
        <a href="http://www.shutdown.cn/post/redis4.0%E6%96%B0%E7%89%B9%E6%80%A7-%E5%86%85%E5%AD%98%E7%A2%8E%E7%89%87%E6%95%B4%E7%90%86/" rel="next" title="">
        <i class="fa fa-chevron-left"></i> 
        </a>
    
    </div>

    <div class="post-nav-prev post-nav-item">
    
        <a href="http://www.shutdown.cn/post/redis5.0%E4%BC%98%E5%8C%96-jemalloc5.1%E4%BA%8Cpurge%E6%94%B9%E8%BF%9B%E5%88%86%E6%9E%90/" rel="prev" title="">
         <i class="fa fa-chevron-right"></i>
        </a>
    
    </div>
</div>
      
     
     
     






    </footer>
  </article>
</section>

          </div>
        </div>
        <div class="sidebar-toggle">
  <div class="sidebar-toggle-line-wrap">
    <span class="sidebar-toggle-line sidebar-toggle-line-first"></span>
    <span class="sidebar-toggle-line sidebar-toggle-line-middle"></span>
    <span class="sidebar-toggle-line sidebar-toggle-line-last"></span>
  </div>
</div>
<aside id="sidebar" class="sidebar">
  <div class="sidebar-inner">

    <section class="site-overview sidebar-panel  sidebar-panel-active ">
      <div class="site-author motion-element" itemprop="author" itemscope itemtype="http://schema.org/Person">
    <img class="site-author-image" itemprop="image"
        src="http://www.shutdown.cn/img/author.jpg"
        alt="不与天斗Domino" />
    <p class="site-author-name" itemprop="name">不与天斗Domino</p>
    <p class="site-description motion-element" itemprop="description"> 
        Programmer &amp; Architect</p>
</div>
      <nav class="site-state motion-element">
    <div class="site-state-item site-state-posts">
      <a href="http://www.shutdown.cn/post/">
        <span class="site-state-item-count">183</span>
        <span class="site-state-item-name">日志</span>
      </a>
    </div>
    <div class="site-state-item site-state-categories">    
        <a href="http://www.shutdown.cn/categories/">      
         
        <span class="site-state-item-count">15</span>
        
        <span class="site-state-item-name">分类</span>
        
        </a>
    </div>

    <div class="site-state-item site-state-tags">
        <a href="http://www.shutdown.cn/tags/">
         
        <span class="site-state-item-count">224</span>
        
        <span class="site-state-item-name">标签</span>
        </a>
    </div>
</nav>
      
      

      

      <div class="links-of-blogroll motion-element inline">
<script type="text/javascript" src="//rf.revolvermaps.com/0/0/8.js?i=&amp;m=0&amp;s=220&amp;c=ff0000&amp;cr1=ffffff&amp;f=arial&amp;l=33&amp;bv=35" async="async"></script>
</div>

    </section>
    
  </div>
</aside>

      </div>
    </main>
   
    <footer id="footer" class="footer">
      <div class="footer-inner">
        <div class="copyright" >
  <span itemprop="copyrightYear">  &copy; 
  2013 - 2023</span>
  <span class="with-love"><i class="fa fa-heart"></i></span>
  <span class="author" itemprop="copyrightHolder">天地维杰网</span>
  <span class="icp" itemprop="copyrightHolder"><a href="https://beian.miit.gov.cn/" target="_blank">京ICP备13019191号-1</a></span>
</div>
<div class="powered-by">
  Powered by - <a class="theme-link" href="http://gohugo.io" target="_blank" title="hugo" >Hugo v0.63.2</a>
</div>
<div class="theme-info">
  Theme by - <a class="theme-link" href="https://github.com/xtfly/hugo-theme-next" target="_blank"> NexT
  </a>
</div>


      </div>
    </footer>

    <div class="back-to-top">
      <i class="fa fa-arrow-up"></i>
      <span id="scrollpercent"><span>0</span>%</span>
    </div>
  </div>

  

<script type="text/javascript">
  if (Object.prototype.toString.call(window.Promise) !== '[object Function]') {
    window.Promise = null;
  }
</script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/jquery/index.js?v=2.1.3"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/fastclick/lib/fastclick.min.js?v=1.0.6"></script> 
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/jquery_lazyload/jquery.lazyload.js?v=1.9.7"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/velocity/velocity.min.js?v=1.2.1"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/vendor/velocity/velocity.ui.min.js?v=1.2.1"></script>
<script src="http://www.shutdown.cn/js/vendor/ua-parser-js/dist/ua-parser.min.js?v=0.7.9"></script>

<script src="http://www.shutdown.cn/js/vendor/fancybox/jquery.fancybox.pack.js?v=2.1.5"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/utils.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/motion.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/affix.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/schemes/pisces.js"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/scrollspy.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/post-details.js"></script>
<script type="text/javascript" src="http://www.shutdown.cn/js/toc.js"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/bootstrap.js"></script>

<script type="text/javascript" src="http://www.shutdown.cn/js/search.js"></script>
<script type="text/x-mathjax-config">
  MathJax.Hub.Config({
    extensions: ["tex2jax.js"],
    jax: ["input/TeX", "output/HTML-CSS"],
    tex2jax: {
      inlineMath: [ ['$','$'] ],
      displayMath: [ ['$$','$$'] ],
      processEscapes: true
    },
    "HTML-CSS": { fonts: ["TeX"] }
  });
</script>
<script src='https://cdnjs.cloudflare.com/ajax/libs/mathjax/2.7.5/MathJax.js?config=TeX-AMS-MML_HTMLorMML' async></script>
</body>
</html>